Results: Algorithm 2
2024-09-01
## Update statistics for results.## [1] "MGS"## [1] "/Users/au618299/programming_projects/minkowski_theory/code/instances/results/algorithm2/MGS-prob-2-100|100-mm-2_1.json"
## [2] "/Users/au618299/programming_projects/minkowski_theory/code/instances/results/algorithm2/MGS-prob-2-100|100-mm-2_2.json"
## [3] "/Users/au618299/programming_projects/minkowski_theory/code/instances/results/algorithm2/MGS-prob-2-100|100-mm-2_3.json"
## [4] "/Users/au618299/programming_projects/minkowski_theory/code/instances/results/algorithm2/MGS-prob-2-100|100-mm-2_4.json"
## [5] "/Users/au618299/programming_projects/minkowski_theory/code/instances/results/algorithm2/MGS-prob-2-100|100-mm-2_5.json"
## [6] "/Users/au618299/programming_projects/minkowski_theory/code/instances/results/algorithm2/MGS-prob-2-100|100-ul-2_1.json"Total time used in computing minimum generator sets (MGS)
Hours used: 105.8972574
IP problems solved: 3
Note:
For all the experiments the minimum generator sets are unique. In particular every generator \(\mathcal{G}\) with corrosponding set \[ (\mathcal{Y}^1, \mathcal{Y}^2... \mathcal{Y}^S)\] we have: \[ \mathcal{Y} = \left\{ y^s \vert \exists y \in \mathcal{Y}_N, c_s = y^s, \forall c \in \mathcal{C}(y) \right\} \] This also implies that the found minimum generator sets are unique minimal generator sets. This is not generally the case as seen in example [ref generatorNotUnique]. It implies however that minimal generator sets are likely to be unique.
STATUS
## [1] 900## # A tibble: 60 × 2
## filename method
## <chr> <chr>
## 1 prob-5-100|100|100|100|100-mmmmm-5_1.json m
## 2 prob-5-100|100|100|100|100-mmmmm-5_2.json m
## 3 prob-5-100|100|100|100|100-mmmmm-5_3.json m
## 4 prob-5-100|100|100|100|100-mmmmm-5_4.json m
## 5 prob-5-100|100|100|100|100-mmmmm-5_5.json m
## 6 prob-5-100|100|100|100|100-uuull-5_1.json ul
## 7 prob-5-100|100|100|100|100-uuull-5_2.json ul
## 8 prob-5-100|100|100|100|100-uuull-5_3.json ul
## 9 prob-5-100|100|100|100|100-uuull-5_4.json ul
## 10 prob-5-100|100|100|100|100-uuull-5_5.json ul
## # ℹ 50 more rowsSolved 900 of 1280`
MGS size as a function of maximum possible size.
## [1] "44%"## [1] "75%"## [1] "86%"For the instances l the MGS tend to consist of all subproblem points. Also for the u instances a large number of the subproblem points are used in the minimum generator sets, however the spread is significantly higher than that of l, and in some cases for u the MGS consists of only half the total subproblem points.
The instances m and ul both contain a larger amount of unsupported and supported points. [TODO Show how many approx 50% of each?]. The difference between the instances are that for m each subset consists of a mix of supported and unsupported points, while the ul instances consists of subsets which have either many unsupported (u), or many supported points (l). For m and ul we find that the MGS is unlikely to consist of all the subproblem points. On average the MGS consists of only 71.66% of the total subproblem points for m instances and 72.62% for ul instances. This implies that around 28% of the generated subproblem points are not needed for generating the nondominated sum.
Relative size of MGS wrt. average subproblem cardinality
In [above] we see that the relative size of the MGS for the instances m and ul decrease in the total number of subproblem points and in the number of subproblems.
For the instances l we see that in almost all instances the MGS consists of all subproblem points.
The u exibit a different pattern from the rest. Here we find that for instances \(p>3\) the MGS tend to consist of all subproblem points. For the remaining instances we find that like ul and m the size of MGS is decreasing in the number of subproblems.
Relative size of MGS wrt. total subproblem cardinality
size of Yn (like for alg1)
classifications
Number of US points in MGS relative to the number of US points in the
subproblems.
Number of supported but non-extreme points removed
Validation
Check that each generator set includes all extreme points:
## # A tibble: 900 × 9
## prob_sizes_se_total prob_sizes_us_total prob_sizes_sne_total
## <dbl> <dbl> <dbl>
## 1 15 185 15
## 2 18 182 18
## 3 20 180 20
## 4 20 180 20
## 5 21 179 21
## 6 85 114 86
## 7 80 119 81
## 8 86 114 86
## 9 86 112 88
## 10 90 110 90
## # ℹ 890 more rows
## # ℹ 6 more variables: MGS_sizes_se_total <dbl>, MGS_sizes_us_total <dbl>,
## # MGS_sizes_sne_total <dbl>, MGS_size <dbl>, prob_total_extreme <dbl>,
## # MGS_total_extreme <dbl>## # A tibble: 900 × 7
## prob_sizes_se prob_sizes_us prob_sizes_sne MGS_sizes_se MGS_sizes_us
## <chr> <chr> <chr> <chr> <chr>
## 1 7-8 93-92 7-8 7-8 57-54
## 2 8-10 92-90 8-10 8-10 49-42
## 3 8-12 92-88 8-12 8-12 61-48
## 4 12-8 88-92 12-8 12-8 48-61
## 5 10-11 90-89 10-11 10-11 41-49
## 6 2-83 98-16 2-84 2-83 4-16
## 7 2-78 98-21 2-79 2-78 11-21
## 8 2-84 98-16 2-84 2-84 8-16
## 9 2-84 98-14 2-86 2-84 9-14
## 10 2-88 98-12 2-88 2-88 9-12
## # ℹ 890 more rows
## # ℹ 2 more variables: MGS_sizes_sne <chr>, MGS_sizes <chr>## # A tibble: 900 × 7
## prob_sizes_se_total prob_sizes_us_total prob_sizes_sne_total
## <dbl> <dbl> <dbl>
## 1 15 185 15
## 2 18 182 18
## 3 20 180 20
## 4 20 180 20
## 5 21 179 21
## 6 85 114 86
## 7 80 119 81
## 8 86 114 86
## 9 86 112 88
## 10 90 110 90
## # ℹ 890 more rows
## # ℹ 4 more variables: MGS_sizes_se_total <dbl>, MGS_sizes_us_total <dbl>,
## # MGS_sizes_sne_total <dbl>, MGS_size <dbl>